package com.company.algo.niuke;

/**【字节，不会】
 * 缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * 思路：数组作为哈希表，桶排序的思想，使得数组中下标为i的数值为i+1.如nums[0]=1,nums[1]=2..
 * 映射关系：nums[i] = i+1
 * 最后遍历数组，如果nums[i]-1!=i，则i+1即为缺失的第一个正数
 * 注意：
 * 交换条件
 * while (nums[i]>0 && nums[i]<=len && nums[i]!=nums[nums[i]-1]){
 * swap(nums,i,nums[i]-1)
 * }
 * 对于遍历到的数 x=nums[i]，如果x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i]和 nums[x−1]，
 * 这样 x 就出现在了正确的位置。在完成交换后，新的 nums[i] 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到
 * x!∈​[1,N]。
 */
public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int x;
            while ((x = nums[i]) > 0 && x <= len && x != nums[x - 1]) {
                swap(nums, x - 1, i);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }

    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
